package tsp;

import java.util.ArrayList;
import java.util.Collections;

public class TSP_MetaHeuristic {

    private final static int NB_METHODES = 5;
    private final static int MUTATION = 1;
    private final static int CROISEMENT_SIMPLE = 2;
    private final static int CROISEMENT_DOUBLE = 3;
    private final static int HEURISTIQUE = 4;
    private final static int ALEATOIRE = 5;
    
    private final static int POURCENTAGE_ALEATOIRE = 90;
    private final static double TAUX_MEILLEURS_RETENUS = 0.05;
    private final static double TAUX_SOLUTIONS_SELECTIONNES = 0.5;
    
    private int nbIterations;
    private final int taillePopulation = 100;
    private TSP_Data tsp_data;
    private TSP_Calcul tsp_calc;
    private ArrayList<TSP_Solution> population;
    private ArrayList<TSP_Solution> solutionsSelectionnees;

    public TSP_MetaHeuristic(TSP_Data tsp_data, boolean withAllLambda, int iterations) {
        this.tsp_data = tsp_data;
        this.nbIterations = iterations;
        tsp_calc = new TSP_Calcul(tsp_data);
        population = new ArrayList<TSP_Solution>();

        genererSolutions();

        algoGenetique();


    }

    /**
     * Génère une liste de nbSolutions solutions et l'ajoute dans listeSolutions
     */
    private void genererSolutions() {
        TSP_Heuristic heuristique;

        for (int i = 0; i < taillePopulation; i++) {
            heuristique = new TSP_Heuristic(tsp_data, true);
            population.add(heuristique.getSolutionRetenue());
        }

        Collections.sort(population, new CostComparator());

    }

    /**
     * Effectue une sélection par tournoi, on fait combattre 2 individus et le
     * meilleur est ajouté à la liste. On ajoute aussi un certain nombre
     * des meilleurs individus sélectionnés d'office.
     * @return la liste des solutions sélectionnées
     */
    public ArrayList<TSP_Solution> tournoi() {

        ArrayList<TSP_Solution> listeSolutionsInitiales;
        listeSolutionsInitiales = (ArrayList<TSP_Solution>) population.clone();
        ArrayList<TSP_Solution> listeSolutionsSelectionnees = new ArrayList<TSP_Solution>();

        int indiceFighter1, indiceFighter2;

        int nbMeilleursRetenus = (int) (taillePopulation * TAUX_MEILLEURS_RETENUS);
        int nbSolutionsSelectionnees = (int) (taillePopulation * TAUX_SOLUTIONS_SELECTIONNES);

        //Retenir un certain nombre des meilleures solutions
        for (int i = 0; i < nbMeilleursRetenus; i++) {
            listeSolutionsSelectionnees.add(listeSolutionsInitiales.get(0));
            listeSolutionsInitiales.remove(0);
        }

        for (int i = nbMeilleursRetenus; i < nbSolutionsSelectionnees; i++) {

            indiceFighter1 = (int) (Math.random() * (listeSolutionsInitiales.size()));

            do {
                indiceFighter2 = (int) (Math.random() * (listeSolutionsInitiales.size()));
            } while (indiceFighter1 == indiceFighter2);

            /* Si la solution 1 est meilleure que la solution 2
            (i.e. si l'indice du fighter1, dans la liste des solutions triées
            par ordre décroissant, est plus petit que celui de fighter2 */
            if (indiceFighter1 < indiceFighter2) {
                listeSolutionsSelectionnees.add(listeSolutionsInitiales.get(indiceFighter1));
                listeSolutionsInitiales.remove(indiceFighter1);
            } else {
                listeSolutionsSelectionnees.add(listeSolutionsInitiales.get(indiceFighter2));
                listeSolutionsInitiales.remove(indiceFighter2);
            }
        }

        //Mélanger la liste
        Collections.shuffle(listeSolutionsSelectionnees);

        return listeSolutionsSelectionnees;

    }

    /**
     * Calcule la meilleure solution avec la méthode de l'algorithme génétique
     */
    private void algoGenetique() {

        int choixMethode;
        TSP_Solution solutionChoisie1 = null;
        TSP_Solution solutionChoisie2 = null;

        for (int i = 0; i < nbIterations; i++) {

            System.out.println("Itération n°" + i + " sur " + nbIterations);

            //Choisir la méthode à appliquer sur les solutions sélectionnées
            choixMethode = (int) (Math.random() * NB_METHODES) + 1;

            //Sélections d'individus sur lesquels appliquer la méthode choisie
            solutionsSelectionnees = tournoi();

            System.out.println("\n\n===POPULATION AVANT (" + population.size() + ") : " + population + "\n\n");

            /* Appliquer la méthode choisie jusqu'à ce que tous les individus
            sélectonnés aient été traités */
            while (!solutionsSelectionnees.isEmpty()) {

                /* Sélection de 2 solutions parmi les individus restants */
                if (solutionsSelectionnees.size() > 1) {
                    solutionChoisie1 = solutionsSelectionnees.get(0);
                    solutionChoisie2 = solutionsSelectionnees.get(1);
                } //Si plus qu'une solution, alors mutation uniquement ou inchangée si croisement
                else {
                    solutionChoisie1 = solutionsSelectionnees.get(0);

                    if (choixMethode != MUTATION && choixMethode != HEURISTIQUE && choixMethode != ALEATOIRE) {
                        population.add(solutionChoisie1);
                        solutionsSelectionnees.remove(0);
                        break;
                    }
                }

                switch (choixMethode) {
                    case MUTATION:
                        System.out.println("Méthode:  MUTATION");
                        population.add(mutation(solutionChoisie1));
                        solutionsSelectionnees.remove(0);
                        break;

                    case CROISEMENT_SIMPLE:
                        System.out.println("Méthode:  CROISEMENT SIMPLE");
                        population.addAll(croisementSimple(solutionChoisie1, solutionChoisie2));
                        solutionsSelectionnees.remove(0); //sol1
                        solutionsSelectionnees.remove(0); //sol2
                        break;

                    case CROISEMENT_DOUBLE:
                        System.out.println("Méthode:  CROISEMENT DOUBLE");
                        population.addAll(croisementDouble(solutionChoisie1, solutionChoisie2));
                        solutionsSelectionnees.remove(0); //sol1
                        solutionsSelectionnees.remove(0); //sol2
                        break;

                    case HEURISTIQUE:
                        System.out.println("Méthode:  HEURISTIQUE");
                        population.add(heuristique(solutionChoisie1));
                        solutionsSelectionnees.remove(0);
                        break;

                    case ALEATOIRE:
                        System.out.println("Méthode:  ALEATOIRE");
                        population.add(aleatoire());
                        solutionsSelectionnees.remove(0);
                        break;
                }
            }

            Collections.sort(population, new CostComparator());

            ArrayList<TSP_Solution> popAux = new ArrayList<TSP_Solution>();
            //Ne garder que les N individus (où N=taille initiale de la population)
            popAux.addAll(population.subList(0, this.taillePopulation));
            population.clear();
            population.addAll(popAux);

            System.out.println("\n\n===POPULATION APRES (" + population.size() + ") : " + population + "\n\n");
        }

    }

    /**
     * Intercroise les deux segments de chaque solution passée en paramètre
     * @param solution1 la solution1 qui sera coupée en 2 segments
     * @param solution2 la solution2 qui sera coupée en 2 segments
     * @return deux nouvelles solutions résultant du croisement
     */
    public ArrayList<TSP_Solution> croisementSimple(TSP_Solution solution1, TSP_Solution solution2) {

        ArrayList<TSP_Solution> nouvellesSolutions = new ArrayList<TSP_Solution>(2);
        ArrayList<Integer> nouveauCycle;

        //Croisement simple si au moins 2 sommets
       if(solution1.getCycle().size() < 2 || solution2.getCycle().size() < 2) {
           nouvellesSolutions.add(solution1);
           nouvellesSolutions.add(solution2);
           return nouvellesSolutions;
       }

        //Calcul des points de croisement pour chaque solution
        int pointCrois1 = (int) (Math.random() * (solution1.getCycle().size() - 1)) + 1;
        int pointCrois2 = (int) (Math.random() * (solution2.getCycle().size() - 1)) + 1;

        ArrayList<Integer> cycle1 = new ArrayList<Integer>();
        ArrayList<Integer> cycle2 = new ArrayList<Integer>();

        /* Croiser segment début de solution1 avec segment fin de solution 2*/

        cycle1.addAll(solution1.getCycle().subList(0, pointCrois1));
        cycle2.addAll(solution2.getCycle().subList(pointCrois2, solution2.getCycle().size()));


        nouveauCycle = genererCycleSimple(cycle1, cycle2);

        nouvellesSolutions.add(creerSolution(nouveauCycle));

        cycle1.clear();
        cycle2.clear();

        /* Croiser segment fin de solution1 avec segment début de solution 2*/

        cycle1.addAll(solution1.getCycle().subList(pointCrois1, solution1.getCycle().size()));
        cycle2.addAll(solution2.getCycle().subList(0, pointCrois2));

        nouveauCycle = genererCycleSimple(cycle2, cycle1);

        nouvellesSolutions.add(creerSolution(nouveauCycle));

        return nouvellesSolutions;
    }

    /**
     * Intercroise les trois segments de chaque solution passée en paramètre
     * @param solution1 la solution1 qui sera coupée en 3 segments
     * @param solution2 la solution2 qui sera coupée en 3 segments
     * @return deux nouvelles solutions résultant du croisement
     */
    public ArrayList<TSP_Solution> croisementDouble(TSP_Solution solution1, TSP_Solution solution2) {

        ArrayList<TSP_Solution> nouvellesSolutions = new ArrayList<TSP_Solution>(2);
        ArrayList<Integer> nouveauCycle;

        //Croisement double possible si au moins 3 sommets
       if(solution1.getCycle().size() < 3 || solution2.getCycle().size() < 3) {
           nouvellesSolutions.add(solution1);
           nouvellesSolutions.add(solution2);
           return nouvellesSolutions;
       }

        int pointCrois1a, pointCrois1b, pointCrois2a, pointCrois2b;

        //Choisir un point de croisement dans la première moitié du cycle
        pointCrois1a = (int) (Math.random() * (solution1.getCycle().size()/2 - 1)) + 1;
        do {
            //Choisir un second point de croisement supérieur au point 1
            pointCrois1b = (int) (Math.random() * (solution1.getCycle().size() - 1)) + 1;
        } while (pointCrois1a >= pointCrois1b);

        pointCrois2a = (int) (Math.random() * (solution2.getCycle().size() / 2 - 1)) + 1;
        do {
            pointCrois2b = (int) (Math.random() * (solution2.getCycle().size() - 1)) + 1;
        } while (pointCrois2a >= pointCrois2b);


        ArrayList<Integer> cycle1 = new ArrayList<Integer>();
        ArrayList<Integer> cycle2 = new ArrayList<Integer>();
        ArrayList<Integer> cycle3 = new ArrayList<Integer>();

        /* Croiser segment du milieu de la solution 2 avec solution 1 */
        cycle1.addAll(solution1.getCycle().subList(0, pointCrois1a));
        cycle2.addAll(solution2.getCycle().subList(pointCrois2a, pointCrois2b));
        cycle2.addAll(solution1.getCycle().subList(pointCrois1b, solution1.getCycle().size()));


        nouveauCycle = new ArrayList<Integer>();
        nouveauCycle = genererCycleDouble(cycle1, cycle2, cycle3);

        nouvellesSolutions.add(creerSolution(nouveauCycle));

        //Réinitialisation
        cycle1.clear();
        cycle2.clear();
        cycle3.clear();

        /* Croiser segment du milieu de la solution 1 avec solution 2 */
        cycle1.addAll(solution2.getCycle().subList(0, pointCrois2a));
        cycle2.addAll(solution1.getCycle().subList(pointCrois1a, pointCrois1b));
        cycle2.addAll(solution2.getCycle().subList(pointCrois2b, solution2.getCycle().size()));


        nouveauCycle = genererCycleDouble(cycle1, cycle2, cycle3);

        nouvellesSolutions.add(creerSolution(nouveauCycle));

        return nouvellesSolutions;
    }

    /**
     * Permute deux sommets dans un cycle
     * @param solution la solution contenant le cycle à faire muter
     * @return la nouveau solution avec le cycle muté
     */
    public TSP_Solution mutation(TSP_Solution solution) {

        //Si le cycle n'a qu'un sommet, mutation impossible
        if(solution.getCycle().size() == 1) return solution;

        TSP_Solution nouvelleSolution = null;
        ArrayList<Integer> cycle;

        int i1, i2; //indice du sommet à muter 1 et du sommet à muter 2

        if(solution.getCycle().size() == 2) {
            i1 = 0;
            i2 = 1;
        }
        else {
            i1 = (int) (Math.random() * (solution.getCycle().size() - 1)) + 1;
            do {

                i2 = (int) (Math.random() * (solution.getCycle().size() - 1)) + 1;
            } while (i1 == i2);
        }

        cycle = (ArrayList<Integer>) solution.getCycle().clone();

        //Ajout du sommet(i2) à la place du sommet(i1)
        cycle.add(i1, solution.getCycle().get(i2));
        cycle.remove(i1 + 1);

        //Ajout du sommet(i1) à la place du sommet(i2)
        cycle.add(i2, solution.getCycle().get(i1));
        cycle.remove(i2 + 1);

        nouvelleSolution = creerSolution(cycle);

        return nouvelleSolution;
    }

    /**
     * Génère un cycle à partir de deux segments de cycles
     * @param cycle1 le premier segment à croiser
     * @param cycle2 le second segment à croiser
     * @return le cycle issu du croisement des deux cycles en entrée
     */
    public ArrayList<Integer> genererCycleSimple(ArrayList<Integer> cycle1, ArrayList<Integer> cycle2) {

        ArrayList<Integer> result = new ArrayList<Integer>();

        result = (ArrayList<Integer>) cycle1.clone();

        for (Integer sommet : cycle2) {
            if (tsp_calc.horsCycle(sommet, result)) {
                result.add(sommet);
            }
        }

        return result;
    }

    /**
     * Génère un cycle à partir de trois segments de cycles
     * @param cycle1 le premier segment à croiser
     * @param cycle2 le segment du milieu
     * @param cycle3 le troisième segment à croiser
     * @return le cycle issu du croisement des trois cycles en entrée
     */
    public ArrayList<Integer> genererCycleDouble(ArrayList<Integer> cycle1,
            ArrayList<Integer> cycle2, ArrayList<Integer> cycle3) {

        ArrayList<Integer> result = new ArrayList<Integer>();

        result = (ArrayList<Integer>) cycle1.clone();

        for (Integer sommet : cycle2) {
            if (tsp_calc.horsCycle(sommet, result)) {
                result.add(sommet);
            }
        }
        for (Integer sommet : cycle3) {
            if (tsp_calc.horsCycle(sommet, result)) {
                result.add(sommet);
            }
        }

        return result;
    }

    /**
     * Crée une solution à partir d'un cycle en calculant les affectations
     * et le coût de la solution
     * @param cycle cycle de la solution
     * @return la solution issue du cycle fourni
     */
    public TSP_Solution creerSolution(ArrayList<Integer> cycle) {
        int[] affectation = tsp_calc.calculerAffectations(cycle);
        int coutSolution = tsp_calc.calculerCoutSolution(cycle, affectation);

        return new TSP_Solution(cycle, affectation, coutSolution);
    }

    private TSP_Solution heuristique(TSP_Solution solution) {
        //Si le cycle a moins de 3 sommets, mutation impossible
        if(solution.getCycle().size() < 4) return solution;

        TSP_Solution nouvelleSolution = null;
        ArrayList<Integer> cycle = new ArrayList<Integer>();

        int i1; //indice du sommet à partir duquel calculer l'heuristique muter
        do {

            i1 = (int) (Math.random() * solution.getCycle().size());
        } while (i1 <= 2);

        //création du cycle initial
        for(int i = 0;i<i1;i++){

            cycle.add(solution.getCycle().get(i));

        }

        //calcul heuristique
        TSP_Heuristic heuri = new TSP_Heuristic(tsp_data, true, cycle);

        nouvelleSolution = heuri.getSolutionRetenue();

        return nouvelleSolution;
    }

    private TSP_Solution aleatoire() {

        ArrayList<Integer> cycle = new ArrayList<Integer>();
        int nbSommets = (tsp_data.getNbSommets()*POURCENTAGE_ALEATOIRE)/100;
        int new_sommet;

        cycle.add(0);
        do {
            new_sommet = (int) (Math.random() * tsp_data.getNbSommets());
            if(!cycle.contains(new_sommet)){
                cycle.add(new_sommet);
            }
        } while (cycle.size()<nbSommets);

        TSP_Solution nouvelleSolution = creerSolution(cycle);

        return nouvelleSolution;
    }
}
